package demo.practice.binary_search;

public class P33 {

    //二分查找
    // 4,5,6,7,0,1,2        任意一个用例在切分为两部分后，都会出现有一部分是有序的
    // 在有序部分的查询可以使用  二分查找  无需部分则使用  再次切分

    //如何判断  切分点 mid在有序  部分还是无序部分
    //4,5,6,7,0,1,2   比如mid==7，前半部分为有序   则有  num[mid]>= num[min] 且 num[mid]>= num[max]  //等于的情况是边界值，元素太少
    //比如mid==0，后半部分为有序   则有  num[mid]<= num[min] 且 num[mid]<= num[max]

    public static void main(String[] args) {
        P33 p33 = new P33();
        p33.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0);
    }

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;

        int min = 0;
        int max = nums.length - 1;

        while (min <= max) {
            int mid = min + (max - min) / 2;
            if (nums[mid] >= nums[min]) {//前面有序
                if (nums[mid] == target)
                    return mid;
                if (target < nums[mid] && target >= nums[min])//target在有序部分（前面部分）
                {
                    max = mid - 1;
                } else {              //target在无序部分（后面部分）
                    min = mid + 1;
                }
            } else { //后面有序
                if (nums[mid] == target)
                    return mid;
                if (target > nums[mid] && target <= nums[max]) {//target在有序部分（后面部分）
                    min = mid + 1;
                } else { //target在无序部分（前面部分）
                    max = mid - 1;
                }
            }
        }
        return -1;
    }


}
